package airthmetic.exercise.queue;


import java.util.Comparator;
import java.util.PriorityQueue;

public class _23_合并K个升序链表 {
    public static ListNode mergeKLists(ListNode[] lists) {
        if(lists == null || lists.length == 0){
            return new ListNode();
        }
//        PriorityQueue<ListNode> queue = new PriorityQueue<ListNode>(new Comparator<ListNode>(){
//                @Override
//                public int compare(ListNode l1, ListNode l2) {
//                    return l1.val - l2.val;
//                }
//        });

        PriorityQueue<ListNode> queue = new PriorityQueue<ListNode>( (l1,l2)->{
            return l1.val - l2.val;
        });


        for(int i=0; i< lists.length; i++){
            queue.offer(lists[i]);
        }

        ListNode res = new ListNode();
        ListNode current = res;
        while(!queue.isEmpty()){
            ListNode n = queue.poll();
            current.next = n;
            current = current.next;
            if(n.next != null){
                n = n.next;
                queue.offer(n);
            }
        }

        return res.next;

    }

    public static void main(String[] args) {
        ListNode listNode1 = new ListNode(1, new ListNode(4, new ListNode(5)));
        ListNode listNode2 = new ListNode(1, new ListNode(3, new ListNode(4)));
        ListNode listNode3 = new ListNode(2, new ListNode(6));

        ListNode[] lists = new ListNode[]{listNode1,listNode2,listNode3};

        ListNode listNode = mergeKLists(lists);
        System.out.println(listNode);

    }
}
